#ifndef __BWLIB_NUMBER_THEORY_FACTORIZATION_H__
#define __BWLIB_NUMBER_THEORY_FACTORIZATION_H__
#include "../config.h"
#include "gcd.h"
#include "module.h"
#include <cstdlib>

namespace bwlib
{
	/* @brief: Pollard-rho 分解因子算法
	           不保证分解的因子是素数，
			   建议在分解前进行素性测试
	   @complexity: O(n^0.25)
	   @param: n, 待分解的数
	   @return: n 的一个非 1 因子 
	   			如果返回 n 表示算法失败 */
	template<typename Type, typename RandFactor>
	inline Type pollard_rho(const Type& n, RandFactor rnd)
	{
		Type x = rnd() % (n - 1) + 1, y = x;
		Type d = 1;
		Type t;
		while(d == 1)
		{
			x = mod_mul(x, x, n) - 1;
			y = mod_mul(y, y, n) - 1;
			y = mod_mul(y, y, n) - 1;

			t = x - y;
			if(t < 0) d = gcd<Type>(-t, n);
			else d = gcd(t, n);
		}

		return d;
	}

	template<typename Type>
	inline Type pollard_rho(const Type& n)
	{
		return pollard_rho(n, std::rand);
	}
}

#endif
